package cn.edu.xjtu.hash.hashTable.isIsomorphic;

import java.util.HashMap;
import java.util.Map;

/**
 * 同构字符串
 * 
 * 给定两个字符串 s 和 t，判断它们是否是同构的。 如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。
 * 每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。 不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。
 */

public class Solution {
  public static void main(String[] args) {
    System.out.println(isIsomorphic("badc", "baba"));
  }

  /**
   * 一个比较巧妙地方法,通过判断对应位置上的两个元素上一次出现的位置是否一样判断两个字符串是否同构
   * 
   * @param s 字符串1
   * @param t 字符串2
   * @return 判断结果
   */
  public boolean isIsomorphic1(String s, String t) {
    Map<Object, Integer> map = new HashMap<>();
    for (Integer i = 0; i < s.length(); i++) {
      if (map.put(s.charAt(i), i) != map.put(String.valueOf(t.charAt(i)), i)) {
        return false;
      }
    }
    return true;
  }

  /**
   * 将两个字符串对应位置上的元素加入哈希表中,在每一次加入前判断对应key和value的对应关系是否一致
   * 
   * @param s
   * @param t
   * @return
   */
  public static boolean isIsomorphic(String s, String t) {
    Map<Character, Character> map = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
      char key = s.charAt(i);
      char value = t.charAt(i);
      // 当包含key的话判断value是否相等
      if (map.containsKey(key)) {
        if (map.get(key) != value) {
          return false;
        }
      } else if (map.containsValue(value)) {
        if (getKey(map, value) != null && getKey(map, value) != key) {
          return false;
        }
      } else {
        // 当不包含的话把这一对键值加到表中
        map.put(key, value);
      }
    }
    return true;
  }

  /**
   * 根据value获取key
   * 
   * @param map   哈希表
   * @param value 需要获取key的value
   * @return 找到的key,没有则返回null
   */
  public static Character getKey(Map<Character, Character> map, char value) {
    Character ret = null;
    for (Character key : map.keySet()) {
      if (map.get(key) == value) {
        ret = key;
      }
    }
    return ret;
  }
}
